#include "stack_queue.h"

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}




// listNode 实现
listNode::listNode(): next(NULL), data(0) {}
listNode::listNode(int nodeData, listNode* succ): next(succ), data(nodeData) {}

// MyStack 实现（无头结点链栈）
MyStack::MyStack(): topNode(NULL), stackSize(0) {}

MyStack::~MyStack(){
    int dummy;
    while(pop(dummy)){}
}

bool MyStack::push(const int& value){
    listNode* node = new (std::nothrow) listNode(value, topNode);
    if(node == NULL) return false;
    topNode = node;
    ++stackSize;
    return true;
}

bool MyStack::pop(int& item){
    if(topNode == NULL) return false;
    item = topNode->data;
    listNode* old = topNode;
    topNode = topNode->next;
    delete old;
    --stackSize;
    return true;
}

bool MyStack::getTop(int& item){
    if(topNode == NULL) return false;
    item = topNode->data;
    return true;
}

// MyQueue 实现（顺序循环队列，预留一个空位）
MyQueue::MyQueue(const int& cap){
    capacity = cap > 0 ? cap : 1; // 容量至少为1（实际可用为 capacity-1）
    queue = new (std::nothrow) int[capacity];
    front = 0;
    rear = 0;
}

MyQueue::~MyQueue(){
    delete [] queue;
    queue = NULL;
    capacity = 0;
    front = rear = 0;
}

bool MyQueue::isFull(){
    return ((rear + 1) % capacity) == front;
}

bool MyQueue::enQueue(const int& value){
    if(isFull()) return false;
    queue[rear] = value;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int& item){
    if(front == rear) return false;
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& item){
    if(front == rear) return false;
    item = queue[front];
    return true;
}

// 工具：运算符优先级
static int opPrecedence(char c){
    if(c == '+' || c == '-') return 1;
    if(c == '*' || c == '/') return 2;
    return -1;
}

// 中缀转后缀
bool postfixExpression(const string& expr, string& result){
    result.clear();
    MyStack opStack; // 存储运算符（以其字符的int值）
    bool hasToken = false;

    for(size_t i = 0; i < expr.size(); ++i){
        char c = expr[i];
        if(c >= '0' && c <= '9'){
            result.push_back(c);
            hasToken = true;
        }else if(c == ' ' || c == '\t' || c == '\r' || c == '\n'){
            continue;
        }else if(c == '('){
            if(!opStack.push((int)c)){
                result = "Expression is wrong!";
                return false;
            }
        }else if(c == ')'){
            int topv;
            bool foundLeft = false;
            while(opStack.getTop(topv)){
                opStack.pop(topv);
                if((char)topv == '('){ foundLeft = true; break; }
                result.push_back((char)topv);
            }
            if(!foundLeft){
                result = "Expression is wrong!";
                return false;
            }
        }else if(c == '+' || c == '-' || c == '*' || c == '/'){
            int topv;
            while(opStack.getTop(topv)){
                char tc = (char)topv;
                if(tc == '(') break;
                int pt = opPrecedence(tc);
                int pc = opPrecedence(c);
                if(pt >= pc){
                    opStack.pop(topv);
                    result.push_back(tc);
                }else{
                    break;
                }
            }
            if(!opStack.push((int)c)){
                result = "Expression is wrong!";
                return false;
            }
            hasToken = true;
        }else{
            result = "Expression is wrong!";
            return false;
        }
    }

    // 出栈剩余运算符
    int v;
    while(opStack.getTop(v)){
        opStack.pop(v);
        if((char)v == '('){
            result = "Expression is wrong!";
            return false;
        }
        result.push_back((char)v);
    }

    if(!hasToken){
        result = "Expression is wrong!";
        return false;
    }

    // 使用后缀表达式进行一次形态校验（栈法）：
    int countStack = 0;
    for(size_t i = 0; i < result.size(); ++i){
        char c = result[i];
        if(c >= '0' && c <= '9'){
            ++countStack;
        }else if(c == '+' || c == '-' || c == '*' || c == '/'){
            if(countStack < 2) {
                result = "Expression is wrong!";
                return false;
            }
            countStack -= 1;
        }else{
            result = "Expression is wrong!";
            return false;
        }
    }
    if(countStack != 1){
        result = "Expression is wrong!";
        return false;
    }

    return true;
}

// 表达式求值
bool expressionVal(const string& expr, int& out){
    out = 0;
    string post;
    if(!postfixExpression(expr, post)){
        out = 0;
        return false;
    }

    MyStack valStack; // 存储整型值
    for(size_t i = 0; i < post.size(); ++i){
        char c = post[i];
        if(c >= '0' && c <= '9'){
            if(!valStack.push((int)(c - '0'))) return false;
        }else{
            int b, a;
            if(!valStack.pop(b)) { out = 0; return false; }
            if(!valStack.pop(a)) { out = 0; return false; }
            long long r = 0;
            switch(c){
                case '+': r = (long long)a + b; break;
                case '-': r = (long long)a - b; break;
                case '*': r = (long long)a * b; break;
                case '/': if(b == 0) { out = 0; return false; } r = a / b; break;
                default: out = 0; return false;
            }
            if(!valStack.push((int)r)) { out = 0; return false; }
        }
    }
    int res;
    if(!valStack.pop(res)) { out = 0; return false; }
    // 栈应为空
    int dummy;
    if(valStack.pop(dummy)) { out = 0; return false; }
    out = res;
    return true;
}

// 杨辉三角（基于 MyQueue）
void yanghui(const int& n){
    if(n <= 0) return;
    // 使用容量足够的队列（n 行最多一行有 n+1 项，算法需要额外空间）
    MyQueue q(max(4, n * 4));
    // 先生成标准行：从第一行"1"开始，但根据题目示例需要从"1,1"开始输出
    q.enQueue(1);
    for(int row = 0; row <= n; ++row){
        // 行生成：使用 0 作为一行终止标记
        q.enQueue(0);
        int prev = 0;
        bool printed = false;
        int x;
        // 输出规则：跳过第一行（只有一个 1）
        string line;
        while(q.deQueue(x)){
            if(x == 0){
                // 一行结束，入队收尾 1，准备下一行
                q.enQueue(1);
                break;
            }
            // 打印本行元素
            if(!line.empty()) line.push_back(',');
            line += to_string(x);
            // 生成下一行元素
            int sum = prev + x;
            q.enQueue(sum);
            prev = x;
            printed = true;
        }
        if(row > 0 && printed){ // 跳过第一行，仅从第二行开始输出
            cout << line << endl;
        }
    }
}
